package mkpsolving;

import java.util.*;

/**
 * User: Julien
 * Date: 18/03/14
 * Time: 10:20
 */
public class Mkp {
    static int i = 0;
    private List<Objet> objetList = new ArrayList<Objet>();
    private List<Objet> objetOrigin = new ArrayList<Objet>();
    private List<Sac> sacList = new ArrayList<Sac>();
    private List<Sac> sacResult = new ArrayList<Sac>();
    private List<NodeMkp> bestKnap = new ArrayList<NodeMkp>();

    public Mkp(List<Objet> objetList, List<Sac> sacList) {
        this.objetList = objetList;
        this.sacList = sacList;
        //Tri de la liste selon le poids/utilité
        Collections.sort(this.objetList);
        objetOrigin = this.objetList;
    }

    /**
     * Retourne la borne supérieure pour le sac s en fonction de la liste des objets
     */
    public double getUpperBound(Sac s) {
        double upperBound = 0;
        double limit = s.getvolume();
        for (Objet o : objetList) {
            // On insère les objets si il reste de la place
            if (limit > o.getpoids()) {
                upperBound += o.getUtil();
                s.getChoix().add(1.0);
                limit -= o.getpoids();
                // si il ne reste pas assez de place pour un objet entier on le fractionne
            } else if (limit > 0) {
                upperBound += (limit) * o.getRapportPU();
                s.getChoix().add(limit / o.getpoids());
                limit = 0;
                // sinon on ajoute pas l'objet (valeur 0.0)
            } else {
                s.getChoix().add(0.0);
            }
        }
        return upperBound;
    }

    /**
     * La fonction lance une rechrche (séparation évaluation) pour chaque sac avec les même objets
     * puis conserve le meilleur résultat sur les sacs évalués et retire le sac et les objets choisis des paramètres d'évaluation
     * et on recommence avec les paramètres restants
     */
    public void solving() {
        // On vérifie qu'il reste des sacs et des objets à évaluer
        if (!sacList.isEmpty() && !objetList.isEmpty()) {
            System.out.println("Liste des objets restants à évaluer:");
            for (Objet objet : objetList) {
                System.out.print(objet + " | P/U = ");
                System.out.print(objet.getRapportPU() + "\n");
            }
            // Pour chaque sac on lance le branch and bound et on recupère le resultat dans une liste
            for (Sac s : sacList) {
                s.getChoix().clear();
                bestKnap.add(evaluateKnap(s, getObjetList()));
            }
            // On appelle une fonction pour trouver le meilleur résultats parmi les résultats obtenus
            keepBestKnap();
        } else {
            if (!sacList.isEmpty()) {
                sacResult.addAll(sacList);
            }
            System.out.println("Fin de la recherche.\n\n");
        }
    }

    /**
     * On recherche la meilleur solution trouvé et on la garde comme optimum
     * on envlève le sac et les objets choisis des paramètres de recherche
     */
    public void keepBestKnap() {
        NodeMkp best = new NodeMkp();
        int id = -1;
        // on balaye tous les résultats et on garde le meilleur
        for (int i = 0; i < bestKnap.size(); i++) {
            if (bestKnap.get(i) != null && (bestKnap.get(i).getEval() > best.getEval())) {
                id = i;
                best = bestKnap.get(i);
            }
        }
        // si le résultat est une solution viable on enlève le sac et les objets des paramètres de recherche
        if (best.getEval() != -1) {
            System.out.println("\n////////Meilleure solution parmi les " + sacList.size() + " sacs restants//////////");
            System.out.println("Sac " + sacList.get(id).getId());
            affichageNode(best);
            System.out.println("////////////////////////////////////\n\n");

            sacList.get(id).setChoix(best.getChoix());
            sacList.get(id).setSolution(true);
            sacList.get(id).setEval(best.getEval());
            List<Objet> temp = new ArrayList<Objet>();
            for (int j = 0; j < best.getChoix().size(); j++) {
                if (best.getChoix().get(j) == 0.0) {
                    temp.add(objetList.get(j));
                } else {
                    sacList.get(id).getChosenObjet().add(objetList.get(j));
                }
            }
            sacResult.add(sacList.get(id));
            objetList = temp;
            sacList.remove(id);
        } else {
            sacResult.addAll(sacList);
            sacList.clear();
        }
        /**on vide la liste des résultats obtenus par la recherche précédente
         *puis on recommence notre évaluation avec les sacs et objets restants*/
        bestKnap.clear();
        solving();
    }

    public NodeMkp evaluateKnap(Sac s, List<Objet> objetList) {
        i = 0;
        NodeMkp best = new NodeMkp();
        NodeMkp temp;
        Deque<NodeMkp> tree = new ArrayDeque<NodeMkp>();
        //premier noeud début de l'arbre de décision
        NodeMkp node = new NodeMkp(getUpperBound(s), s.getChoix());
        // on calcule l'optimum du noeud racine
        node.findOptimum(s, objetList);
        // on l'ajoute à larbre de décision (Pile)
        tree.addFirst(node);
        //Tant que tous les noeuds de l'arbre n'ont pas été evalués on poursuit notre recherche
        do {
            // On regarde si notre premier noeud peut être branché
            tree.getFirst().evaluateBranching();
            //si oui et que notre noeud actuel et plus intéressant notre meilleur solution
            if (tree.getFirst().getPossibleBranch() != -1 && tree.getFirst().getEval() >= best.getEval()) {
                temp = tree.getFirst();
                // On vérifie si ce noeud peut être une solution valable (solution entière) si c'est le cas il devient notre meilleur solution
                if (((temp.getEval() == Math.floor(temp.getEval())) && !Double.isInfinite(temp.getEval())) && temp.isSolution()) {
                    if (temp.getEval() > best.getEval()) {
                        best = temp;
                    }
                }
                //comme le noeud  courant peut être branché on construit son fils gauche et son fils droit
                NodeMkp nLeft = new NodeMkp(tree.getFirst(), true);
                NodeMkp nRight = new NodeMkp(tree.getFirst(), false);
                tree.removeFirst();
                tree.addFirst(nLeft);
                // on ajoute en dernier le fils droit dans la pile afin qu'il soit le prochain à être évalué (parcours en profondeur)
                tree.addFirst(nRight);
                i++;
            } else {
                // dans le cas où le noeud courant ne peut pas être branché ou que son optimum soit inférieur à notre meilleur solution
                temp = tree.getFirst();
                // on évalue si il est une solution viable
                if (((temp.getEval() == Math.floor(temp.getEval())) && !Double.isInfinite(temp.getEval()))) {
                    if (temp.getEval() > best.getEval()) {
                        best = temp;
                    }
                }
                //puis on le retire de notre arbre
                tree.removeFirst();
                i++;
            }
            // si l'arbre (pile) n'est pas entièrement exploré on évalue le prochain noeud
            if (!tree.isEmpty()) {
                tree.getFirst().findOptimum(s, objetList);
            }
        } while (!tree.isEmpty());
        //si à la fin de notre recherche on a obtenue une solution viable on la retourne
        if (best.getEval() != -1) {
            return best;
        } else {
            return null;
        }
    }

    //Cette fonction affiche le bénéfice et les objets choisi pour un noeud solution
    public void affichageNode(NodeMkp n) {
        System.out.println("Bénéfice : " + n.getEval());
        for (int j = 0; j < n.getChoix().size(); j++) {
            if (n.getChoix().get(j) == 1.0) {
                System.out.println(objetList.get(j).toString());
            }
        }
        System.out.println("Solution trouvé après " + i + " branchement(s)");
    }


    public List<Objet> getObjetList() {

        Collections.sort(objetList);
        return objetList;
    }

    public List<Sac> getSacResult() {
        return sacResult;
    }

    public List<Objet> getObjetOrigin() {
        return objetOrigin;
    }
}

